\section{Integration gewöhnlicher Differentialgleichungen}

Die Behandlung von Differentialgleichungen spielt in der Numerik eine zentrale Rolle. Die mathematische Modellierung von zeitabhängigen Vorgängen führt vielfach auf Systeme von Differentialgleichungen (Biologie, Mechanik, Wirtschaft). Hängen die Zustandsgrößen nur von der Zeit ab, so spricht man von \emph{gewöhnlichen Differentialgleichungen}, hängen sie auch vom Ort ab, so spricht man von \emph{partiellen Differentialgleichungen}. Da die analytische Lösung meist nicht explizit berechenbar ist, ist man auf numerische Approximationen angewiesen.

\subsection{Aufgabenstellung und einfache Einschrittverfahren}

\begin{example} 
	Idealisiertes Pendel
	\begin{align}
		\nonumber m l \phi &= -m g \sin(\phi)\\
		\nonumber \phi(0) &= \alpha\\
		\nonumber \dot{\phi}(0) &= 0
	\end{align}
	Wobei $l$ die Länge des Pendels angibt, $m$ die Masse des Massepunkts am Ende des Pendels und $\phi$ die Auslenkung des Pendels.
\end{example}

\begin{example} 
	Lotka-Volterra (Räuber-Beute-Modell)
	\begin{align}
		\nonumber\dot{y}_1 &= c_1y_1(1-\alpha_1y_2)\\
		\nonumber\dot{y}_2 &= c_2y_2(\alpha_2y_1-1)
	\end{align}
		
	Mit $c_1, c_2, \alpha_1, \alpha_2 > 0$ und Anfangswerten $y_1(0) = y^0_1$ und $y_2(0) = y^0_2$.
\end{example}

\begin{example} 
	Dreikörperproblem (Euler 1772)
\end{example}

\begin{definition}[Definition IV.1]
	Gesucht sei 
	$y(t), t \in [t_0, T], y \in \mathbb{R}^n$ mit 
	$$y^{(m)} = f(t, \dot{y}, \ddot{y}, ..., y^{(m-1)})$$
	und
	$$y(t_0) = t_0, \dot{y}(t_0) = z_1, ..., y^{(m-1)}(t_0) = t_{m-1}.$$
	
	Dies definiert ein Anfangswertproblem m-ter Ordnung.
\end{definition}

Die meisten numerischen Verfahren betrachten Anfangswertprobleme 1. Ordnung. Dies ist ausreichend da jedes System der Größe n von m-ter Ordnung in ein System der Größe $n \cdot m$ von 1-ter Ordnung überführt werden kann.

$$y_1(t) = y(t)$$
$$y_2(t) = \dot{y}(t) = \dot{y}_1(t)$$
$$y_3(t) = \ddot{y}(t) = \dot{y}_2(t)$$
$$\vdots$$
$$y_m(t) = y^{(m-1)}(t) = \dot{y}_{m-1}(t)$$

Im Folgenden gehen wir von korrekt gestellten Problemen aus (Hadamard):

\begin{itemize}
	\item Existenz einer Lösung (Satz von Peano)
	\item Eindeutigkeit der Lösung (Satz von Picard-Lindelöf)
	\item Stetige Abhängigkeit der Lösung von den Daten (Lemma von Gronwall)
\end{itemize}

Von nun an betrachten wir Anfangswertprobleme 1. Ordnung der Form:

\begin{quote}
	Gesucht: 
	$$y: [t_0, T] \rightarrow \mathbb{R}^n$$ mit 
	$y = f(t, y)$, $y(t_0) = y_0$ und f Lipschitzstetig in y
	$$\|f(t,y_1) - f(t,y_2)\| \le L \|y_1 - y_2\|$$
\end{quote}

Die Grundidee aller numerischer Verfahren ist die Zerlegung in eine endliche Anzahl von Teilintervallen $[t_1, t_{i+1}]$, $i = 0, ... N-1$ mit $t_0 < t_1 < ... < t_N = T$. Mit $h_i = t_{i+1} - t_i$ bezeichnet man die Zeitschrittweite. Nun wird für jedes $i$ eine Approximation $y_i$ von $y(t_i)$ gesucht. Eine Vielzahl von Verfahrensklassen basiert auf Integration, Numerischer Quadratur, Extrapolation.

\begin{align}
	\nonumber y(t_{i+1}) - y(t_i) &= \int_{t_i}^{t_{i+1}}\!\dot{y}(t)\,dt \\
	\nonumber &= \int_{t_i}^{t_{i+1}}\!f(t, y(t))\,dt \\
	\nonumber &=: I_i
\end{align}

Man kann $I_i$ ersetzen durch

\begin{enumerate}
	\item[1)] $I_i \approx h_i f(t_i, y(t_i))$ 
	\item[2)] $I_i \approx h_i f(t_{i+1}, y(t_{i+1}))$ 
	\item[3)] $I_i \approx \frac{h_i}{2} (f(t_i, y(t_i)) + f(t_{i+1}, y(t_{i+1})))$ (Trapezregel)
	\item[4)] $I_i \approx h_i f(t_{i+\frac{1}{2}}, y(t_{i+\frac{1}{2}}))$
	\item[5)] $I_i \approx \frac{h_i}{2} (f(t_i, y(t_i)) + f(t_i, y(t_i)) + h_i \frac {f(t_i,y(t_i))-f(t_{i-1}, y(t_{i-1}))}{h_{i-1}})$
\end{enumerate}

Im nächsten Schritt werden die unbekannten Funktionswerte $y(t_l),  = i, i+1, i-1$ durch ihre jeweiligen numerischen Approxomationen $y_l$ ersetzt. Dies definiert $y_{i+1}$

\begin{enumerate}
	\item[1)] $y_{i+1} = y_i + h_i f(t_i, y_i)$ (expliziter Euler, forward Euler)
	\item[2)] $y_{i+1} = y_i + h_i f(t_{i+1}, y_{i+1})$ (impliziter Euler, backward Euler)
	\item[3)] $y_{i+1} = y_i + \frac{h_i}{2} (f(t_i, y_i) + f(t_{i+1}, y_{i+1}))$ (Crank-Nicolson)
	\item[4)] $y_{i+1} = y_i + h_i f(t_{i+\frac{1}{2}}, y_{i+\frac{1}{2}})$ (Mittelpunktsregel) \\
		Spezialfall $h_i = h$: $y_{i+\frac{1}{2}} = y_{i-\frac{1}{2}} + h f(t_i, y_i)$
	\item[5)] Sei $h_i = h$. $y_{i+1} = y_i + h (\frac{3}{2} f(t_i, y_i) - \frac{1}{2} f(t_{i-1}, y_{i-1}))$ (Adams-Bashforth Typ)
\end{enumerate}

Ersetzt man im Verfahren 3 bzw. 4 auf der rechten Seite $y_{i+1}$ bzw $y_{i+\frac{1}{2}}$ durch die Approximation aus einem expliziten Euler Schritt mit $h_i$ bzw. $\frac{h_i}{2}$, so erhält man

\begin{enumerate}
	\item[$3_{mod}$)] $y_{i+1} = y_i + \frac{h_i}{2} (f(t_i, y_i) + f(t_{i+1}, y_i + h_i f(t_i, y_i)))$ (Heun)
	\item[$4_{mod}$)] $y_{i+1} = y_i + h_i f(t_{i+\frac{1}{2}}, y_i + \frac{h_i}{2} f(t_i, y_i))$ (modifiziertes Eulerverfahren)
\end{enumerate}

Frage: 
\begin{itemize}
	\item Wie können die Methoden klassifiziert werden?
	\item Liegen Abschätzungen der Form $\|y(t_i) - y_i\| = O(h^p), h = \!\displaystyle\max_{i=0..N-1}{h_i}$ vor?
\end{itemize} 

\begin{definition}[Definition IV.2]
	Klassifizierung
	\begin{enumerate}
		\item Ein Verfahren heißt explizit, falls $y_{i+1}$ durch Funktionsauswertungen von $f$ direkt bestimmt werden kann (Verfahren 1, 4, 5, $3_{mod}$, $4_{mod}$. Andernfalls heißt es implizit.
		\item Ein Verfahren heißt Einschrittverfahren falls $y_{i+1}$ nur von $y_i$ abhängt (Verfahren 1, 2, 3, $3_{mod}$, $4_{mod}$). Hängt $y_{i+1}$ von den Werten $y_i, ..., y_{i-k+1}$ ab, so heißt es (k-Schritt) Mehrschrittverfahren.  
	\end{enumerate}
\end{definition}

\subsection{Konvergenz von Einschrittverfahren}

Ein allgemeines Einschrittverfahren kann in der Form 
$$y_{i+1} = y_i + h_i \phi (t_i, h_i, y_i, y_{i+1}; f)$$

dargestellt werden. $\phi$ nennt man dann Verfahrensfunktion oder Inkrementfunktion. 

\begin{example} Für die Verfahrensfunktion des expliziten Euler gilt:

	$$\phi_1(t_i, h_i, y_i, y_{i+1}) = f(t_i, y_i)$$
	
	Für die Verfahrensfunktion des impliziten Euler gilt:
	
	$$\phi_2(t_i, h_i, y_i, y_{i+1}) = f(t_{i+1}, y_{i+1})$$

\end{example}

%% 25. Juni 2010

\begin{definition}[Definition IV.3] 
	Ein Einschrittverfahren mit der Verfahrensfunktion $\phi$ heißt konvergent von der Ordnung p, falls gilt: der Fehler $e_i(t_j) := y(t_j) - y_j$ erfüllt 
	
	$$\|e_h\|_\infty = \OO{h^p}, \|e_h\|_\infty = \displaystyle\max_{j=0, \dots N_h}\|e_i(t_j)\|$$
	
	unter der Voraussetzung, dass 
	
	$$t_{N_h} = T, n = \max_i h_i, f \in C^p$$
\end{definition}

\begin{remark}
	Anschaulich einleuchtend ist, dass der Fehler $e_h$ sich aus zwei Komponenten zusammensetzt
	
	\begin{enumerate}
		\item[a)] lokaler Abbruchfehler (Konsistenzfehler)
		\item[b)] Fehlerfortpflanzungsoperator
	\end{enumerate}
\end{remark}

\subsubsection{Lokaler Abbruchfehler}

\begin{definition}[Definition IV.4] Konsistenzfehler
	\begin{enumerate}
		\item
			Sei $z(t, t_\alpha, y_\alpha)$ die Lösung des Anfangswertproblems 
		
			$$\dot{y} = f(T,y)$$
			$$y(t_\alpha) = y_\alpha$$
		
			und $z_h$ sei die numerische Lösung aus einem Schritt des Einschrittverfahrens, das heißt, 
			
			$$z_n(t, t_\alpha, y_\alpha) = y_\alpha + (t - t_\alpha) \; \phi(t_\alpha, t-t_\alpha, y_\alpha).$$
			
			Dann heißt die Differenz 
			
			$$\delta(t_\alpha, y_\alpha, h) := z(t_\alpha + h, t_\alpha, y_\alpha) - z_h(t_\alpha + h, t_\alpha, y_\alpha)$$
			
			lokaler Abbruchfehler zum Startwert $(t_\alpha, y_\alpha)$.
		\item
			Der relative lokale Fehler
			$$\tau(t_\alpha, y_\alpha, h) = \frac{1}{h}\delta(t_\alpha, y_\alpha, h)$$
			heißt Konsistenzfehler.
			
		\item
			Ein Verfahren heißt konsistent, falls 
			
			$$\tau(t_\alpha, y_\alpha, h) \to 0, h \to 0$$
			
			gleichmäßig in $(t_\alpha, y_\alpha)$.
			
		\item
			Ein Einschrittverfahren heißt konsistent von der Ordnung p, falls 
			
			$$\|\tau(t_\alpha, y_\alpha, h)\| \le C h^p, h \le H$$ 
			
			für alle Punkte $(t_\alpha, y_\alpha)$ in der Umgebung einer hinreichend glatten Lösungskurve ($y \in C^{p+1}$).
	\end{enumerate}
\end{definition}

Das zentrale Hilsmittel zur Bestimmung der Konsistenzordnung ist die Taylorentwicklung.

\begin{lemma}
	Ein Einschrittverfahren ist genau dann konsistent, falls für $h \to 0$ gilt:
	
	$$\phi(t,h,y) \to f(t,y)$$
\end{lemma}	

\begin{proof}
	\begin{align*}
		z(t+h, t, y) &= z(t,t,y) + \dot{z}(t,t,y)(t+h-t) + \OO{h^2} \\
		&= y + f(t,y) h + \OO{h^2} \\
		\tau(t,y,h) &= \frac{1}{h} (z(t+h, t, y) - y - h \phi (t,h,y)) \\
		 &= \underbrace{f(t,y) - \phi(t,h,y)}_{\to 0} + O(h) 
	\end{align*}
\end{proof}

\begin{example}
	\*
	\begin{enumerate}
		\item
			Der expliziter Euler ist von Konsistenzordnung 1:
			
			\begin{align*}
				\tau\left(t,y,h\right) &= \frac{1}{h} \left(y + f\left(t,y\right) h + \frac{1}{2} \left(f_t\left(t,y\right) + f_y\left(t,y\right) f\left(t,y\right)\right) h^2 + \OO{h^3} - y - hf\left(t,y\right)\right) \\
				& = \frac{1}{2} \left(f_t\left(t,y\right) + f_y\left(t,y\right) f\left(t,y\right)\right) h + \OO{h^2} 
			\end{align*}
			
		\item
			Das Verfahren von Heun ist von Konsistenzordnung 2:
			
			\begin{align*}
				z(t+h,t,y) &= y+f h + \frac{1}{2} h^2 (f_t + f_yf) + \frac{1}{6} h^3(f_{tt} + f_{ty}f + f_{yt} f + f_{yy}f^2 + f_yf_t + f_y^2 f) + \OO{h^4} \\
				\phi(t,h,y) &= \frac{1}{2} ( f(t,y) + f(t+h, y+hf(t,y))) \\
				&= \frac{1}{2} (f + f + hf_t + h f f_y + \frac{1}{2} h^2 f_{tt} + \frac{1}{2}  h^{2} f f_{ty}+ \frac{1}{2}  h^{2} f f_{yt} + \frac{1}{2} h^2 f^2 f_{yy} + \OO{h^3})
			\end{align*}
			
			Daraus folgt:
			
			\begin{align*}
				\tau(t,y,h) = \frac{1}{h} &(y + hf + \frac{1}{2} h^2 f_t + \frac{1}{2} h^2 f_yf + \frac{1}{6} h^3 f_{tt} + \frac{1}{3} h^{3} f_{ty}f + \frac{1}{6} h^3 f_{yy} f^2 + \frac{1}{6} f_yf_t + \frac{1}{6} h^3 f_y^2 f \\
				- &(y + hf + \frac{1}{2} h^2 f_t + \frac{1}{2} h^2 f_yf +\frac{1}{4}h^3 f_{tt}+ \frac{1}{2} h^3 ff_{ty} + \frac{1}{4} h^3 f^2f_{yy})) + \OO{h^3}
			\end{align*}
	\end{enumerate}
\end{example}

Die beiden Beispiele haben bereits die Problematik aufgezeigt, die eintritt, falls man Einschrittverfahren höherer Ordnung konstruieren will. 

Allgemein gilt: ein Einschrittverfahren der Konsistenzordnung $\ge p$ erfordert 

$$\frac{\operatorname{d}^{l+1}}{\operatorname{d}t^{l+1}} y(t) = \frac{\operatorname{d}^{l}}{\operatorname{d}t^{l}} g(t,y(t)) = \left. (l+1) \frac{\partial^l}{\partial^l h} \phi (t,h,y) \right|_{h = 0} \forall l=0, \dots, p-1$$ 

Da beim Ableiten Produkt- und Kettenregel berücksichtigt werden müssen, wächst die anzahl der Terme, die man erhält, exponentiell in $p$ an.

\subsubsection{Globaler Diskretisierungsfehler}

Bei Einschrittverfahren existiert ein elementarer Zusammenhang zwischen Konsistenz und Konvergenz.

\begin{definition}[Definition IV.5] (Null-)Stabilität: Ein Einschrittverfahren heißt Null-stabil, falls ein $H_0 > 0$ existiert und ein $C < \infty$ existiert, so dass für alle $\epsilon > 0$ gilt:

	$$\|y_i - z_i\| \le C \epsilon \;\;\;\forall i \le N_h,\;\;h \in \left(0,H_0\right],\;\;t_{N_h} = T$$

	falls
	
	\begin{align*}
		y_{i+1} &= y_i + h_i \phi (t_i, h_i, y_i) \\
		z_{i+1} &= z_i + h_i (\phi (t_i, h_i, y_i) + \delta_{i+1}) \\
		z_0 &= y_0 + \delta_0 \\
	\end{align*}
	
	mit $\|\delta_i\| \le \epsilon$

\end{definition}

% 29. Juni 2010

Im Gegensatz zu anderen Stabilitätsbegriffen wird bei der Null-Stabilität der Grenzwert $h \to 0$ betrachtet.

\begin{theorem}
	Sei $\phi$ eine Verfahrensfunktion eines expliziten Einschrittverfahrens mit $\phi$ Lipschitzstetig in $y$, so ist das Einschrittverfahren Null-stabil.
\end{theorem}

\begin{proof} wir betrachten den Spezialfall $h_i = h$. Definiere

	$$w_{i+1} = z_{i+1} - y_{i+1}$$

	so gilt:
	\begin{align*}
		w_{i+1} &= w_i + h(\underbrace{\phi(t_i, h, z_i) - \phi(t_i, h, y_i)}_{\le L \|z_i - y_i\| = L \|w_i\|} + \delta_{i+1})\\
		\|w_{i+1}\| &\le (1 + hL) \|w_i\| + h\|\delta_{i+1}\| \\
		& \le (1+hL)\|w_i\| + h\epsilon
	\end{align*}
	
	Damit ist das Lemma von Gronwall anwendbar mit 
	
	\begin{align*}
		a = hL, b = h\epsilon &\rightarrow \|w_i\| \le \|w_0\| e^{N_h hL} + \frac{\epsilon}{L}\left(e^{N_h hL} - 1\right) \;\;\; i = 0, \dots, N_h, N_h = \frac{T - t_0}{h}\\
		&\rightarrow \|w_i\| \le \left(1 + \frac{1}{L}\right) \epsilon e^{(T-t_0)L}
	\end{align*}
\end{proof}

Kombiniert man Stabilität und Konsistenz, erhält man eine obere Schranke für den Fehler.

\begin{theorem}
	Konvergenzordnung. Ein von der Ordnung $p$ konsistentes Einschrittverfahren mit Lipschitzstetiger Verfahrensfunktion ist konvergent mit
	
	$$\|e_h\| \le Ch^p$$
	
	falls
	
	$$f \in C^{p+1}$$
\end{theorem}

\begin{proof}
	Definiere $z_i = y(t_i)$, so erhält man 
	
	\begin{align*}
		z_{i+1} &= y(t_{i+1}) \\
		&= y(t_i) + h_i \phi(t_i, h_i, y(t_i)) + h_i \tau(t_i, y(t_i), h_i)\\
		&= z_i + h_i(\phi(t_i, h_i, z_i) + \underbrace{\tau(t_i, z_i, h_i)}_{\delta_{i+1} mit \|\delta_{i+1}\| \le Ch^p})
	\end{align*}
	
	Da das Verfahren nach Satz IV.2 Null-stabil ist, gilt:
	
	$$\|e_h\|_\infty = \|y(t_i) - y_i\|_\infty \le C\epsilon \le Ch^p$$
\end{proof}

Faustregel: Konsistenz + Stabilität = Konvergenz.

\begin{remark}
	Die theoretischen Ergebnisse berücksichtigen keine Rundungsfehler. Das heißt
	
	$$y_{i+1} = y_{i} + h_i \left(\phi\left(t_i, h_i, y_i\right) + \underbrace{eps}_{Maschinengenauigkeit} / h_i \right)$$
	
	unter Berücksichtigung von Rundungsfehlern:
	
	$$\|e_h\|_\infty \le C\left(h^p + \frac{eps}{h}\right)$$
	
	\begin{enumerate}
		\item Man erhält keine numerischen Approximationen in Maschinengenauigkeit ($\OO{eps^{\frac{p}{p+1}}}$)
		\item Der Effekt, dass der Fehler wieder anwächst, tritt umso früher ein, desto größer p.
		
		$$h^p = \frac{eps}{h}\;\;\;\;\;\;h = \sqrt[p+1]{eps}$$
	\end{enumerate}
\end{remark}

Frage: Wie erhält man Verfahren von höherer Ordnung?

Idee: Setze $\phi$ gleich den ersten $p$ Gliedern der Taylorentwicklung von $y(t + h) - y(t)$.

\begin{tabular}{ l l }
	$p=1 \;\;\;\;\;\;\;\;$ & $\phi(t,h,y) = f(t,y)$\\
	$p=2 \;\;\;\;\;\;\;\;$ & $\phi(t,h,y) = f(t,y) + \frac{1}{2} (f_t(t,y) + f_y(t,y) f(t,y))$
\end{tabular}

Die Idee ist numerisch schlecht:

\begin{enumerate}
	\item Ableitungen der rechten Seite werden explizit benötigt.
	\item Der Aufwand steigt exponentiell in p.
\end{enumerate}

Die Klasse der Runge-Kutta Verfahren stellt eine attraktive Alternative dar.

\subsection{Runge-Kutta Verfahren}

Die Verfahren von Runge und Kutta sind Verallgemeinerungen der bisher betrachteten Einschrittverfahren. Die Zentrale Idee ist: berechne $y_{i+1}$ aus $y_i$ und einer gewichteten Summe von Approximationen an die Steigung von $y(t)$ an Teilknoten $t_{ij} \in [t_i, t_i + h_i]$.

\begin{definition}[Definition IV.6] Runge-Kutta Verfahren.
	\begin{enumerate}
		\item Ein allgemeines Runge-Kutta Verfahren hat die Form
		
		$$y_{i+1} = y_i + h_i \sum_{j=1}^s \gamma_j k_j, s \in \mathbb{N}$$
		
		s heißt Stufe des Runge-Kutta Verfahrens und die $k_j$ sind definiert
		
		$$k_j := f(t_{ij}, y_i + h_i \sum_{l=1}^s \beta_{jl} k_l)$$
		
		mit
		
		$$t_{ij} = t_i + \alpha_j h_i$$
		
		und
		
		$$\alpha_j, \beta_{jl}, \gamma_j \in \mathbb{R} \;\;\;\; 1 \le j, l \le s$$ 
		
		\item Die kompakte Matrixdarstellung 
		
		$$\begin{array}{c|ccc}
			\alpha_1 & \beta_{11} & \dots & \beta_{1s} \\
			\vdots   & \vdots     &       & \vdots \\
			\alpha_s & \beta_{s1} & \dots & \beta_{ss} \\
			\hline
			         & \gamma_{1} & \dots & \gamma_{s} 
		\end{array}$$
		
		heißt Butcher-Schema.
	\end{enumerate}
\end{definition}

\begin{example}
	Butcher-Schema für bisher eingeführte Verfahren:
	
	\begin{enumerate}
		\item Expliziter Euler
				$$\begin{array}{cc}
			0 & 0\\
			  & 1
		\end{array}$$

		\item Impliziter Euler
				$$\begin{array}{cc}
			1 & 1\\
			  & 1
		\end{array}$$
		
	\end{enumerate}
\end{example}

\begin{theorem}
	Konsistenz von RKV
	\\
	Ein RKV ist genau dann konsistent, falls
	$$\sum_{j=1}^{s}\gamma_{j}=1$$
\end{theorem}

\begin{theorem}
	Ordnungsschranke für explizite RKV
	\\
	Ein $s$-stufigeds RKV, welches explizit ist, hat die Ordnung $p\le s$
\end{theorem}

\begin{remark}
	\begin{enumerate}
		\item Es gibt keine Formel, die für alle $p$ einen Zusammenhang zwischen $p$ und $s_{min}$ liefert (bei expliziten RKV)
		\item Es gibt explizite RKV beliebig hoher Ordnung ($\rightarrow$ Extrapolationsschemata)
	\end{enumerate}
\end{remark}

Im folgenden betrachten wir nur noch Verfahren mit $$\alpha_{j}=\sum_{l=1}^{s}\beta_{j,l}$$
Motivation: Ein RKV ist invariant bezüglich der Transformation des AWP auf ein autonomes System (keine Zeitabhängigkeit der rechten
Seite von der Zeit):

$\dot y = f(t,y), y(t_{0})=y_{0}\Rightarrow \left ( \begin{array}{c}
\dot y\\
\dot z
\end{array} \right ) = \left (
\begin{array}
{c}
	f(z,y)\\
	1
\end{array} \right )$ mit $y(t_{0})=y_{0}$ und $z(t_{0})=t_{0}$
genau dann, falls $\alpha_{j}=\sum_{l=1}^{s}\beta_{j,l}$ gilt.

Daraus folgt, dass man noch $\frac{s(s-1)}{2}+(s-1)$ Freiheitsgrade hat.

\begin{theorem}
	Ordnungsgleichungen
	\\
	Gegeben sind folgende Gleichungen:
	\begin{enumerate}
		\item $\sum_{l=1}^{s}\gamma_{l}=1$
		\item $\sum_{l=1}^{s}\gamma_{l}\alpha_{l}=\frac{1}{2}$
		\item $\sum_{l=1}^{s}\gamma_{l}\alpha_{l}^{2}=\frac{1}{3}$
		\item $\sum_{l,k}^{s}\gamma_{l}\beta_{l,k}\alpha_{k}=\frac{1}{6}$
		\item $\sum_{l=1}^{s}\gamma_{l}\alpha_{l}^{3}=\frac{1}{4}$
		\item $\sum_{l,k}^{s}\gamma_{l}\alpha_{l}\beta_{l,k}\alpha_{k}=\frac{1}{8}$
		\item $\sum_{l,k}^{s}\gamma_{l}\beta_{l,k}\alpha_{k}^{2}=\frac{1}{12}$
		\item $\sum_{l,k,j}^{s}\gamma_{l}\beta_{l,k}\beta_{k,j}\alpha_{j}=\frac{1}{24}$
	\end{enumerate}
	Dann gelten folgende Ordnungsaussagen:
	\begin{itemize}
		\item Gilt 1) $\Rightarrow p\ge 1$
		\item Gelten 1) + 2) $\Rightarrow p\ge 2$
		\item Gelten 1) - 4) $\Rightarrow p\ge 3$
		\item Gelten 1) - 8) $\Rightarrow p \ge 4$
	\end{itemize}
\end{theorem}


\begin{example}
	\*
	\begin{enumerate}
		\item 2-stufiges explizites RKV der Ordnung $p=2$
			$$\begin{array}{c|cc}
				0 & 0 & 0\\
				\alpha & \alpha & 0\\
				\hline
				  & 1-\frac{1}{2\alpha} & \frac{1}{2\alpha}
			\end{array}$$
		\item 2-stufiges implizites RKV der Ordnung $p=4$ (Hammer \& Hollingworth)
			$$\begin{array}{c|cc}
				\frac{1}{2} - \frac{1}{2}\sqrt{\frac{1}{3}} & \frac{1}{4} & \frac{1}{4} - \frac{1}{2}\sqrt{\frac{1}{3}}\\
				\frac{1}{2} + \frac{1}{2}\sqrt{\frac{1}{3}} & \frac{1}{4} + \frac{1}{2}\sqrt{\frac{1}{3}} & \frac{1}{4}\\
				\hline
				  & \frac{1}{2} & \frac{1}{2}
			\end{array}$$	
		\item 4-stufige explizite RKV der Ordnug 4
			\begin{itemize} 
				\item $\frac{3}{8}$-Regel
					$$\begin{array}{c|cccc}
						0           &              &             &             & \\
						\frac{1}{3} &  \frac{1}{3} &             &             & \\ 
						\frac{2}{3} & -\frac{1}{3} &           1 &             & \\
						1           &            1 &          -1 &           1 & \\ 
						\hline
						            &  \frac{1}{8} & \frac{3}{8} & \frac{3}{8} & \frac{1}{8}
					\end{array}$$
				\item Kuntzmann
					$$\begin{array}{c|cccc}
						0           &                &                 &                 & \\
						\frac{2}{5} &    \frac{2}{5} &                 &                 & \\ 
						\frac{3}{5} &  -\frac{3}{20} &     \frac{3}{4} &                 & \\
						1           &  \frac{19}{44} &  -\frac{15}{44} &   \frac{40}{44} & \\ 
						\hline
						            & \frac{55}{360} & \frac{125}{360} & \frac{125}{360} & \frac{55}{360}
					\end{array}$$
			
			\end{itemize}
	\end{enumerate}
\end{example}

Frage: Wie können RKV höherer Ordnung konstruiert werden?
\begin{enumerate}
	\item Extrapolationstechniken ($\rightarrow$ explizite RKV)
	\item Kollokationstechniken ($\rightarrow$ i.d.R. implizite RKV)
\end{enumerate}

\subsubsection{Kollokationsmethoden}

Idee: Definiere ein Polynom $q_i$ vom Grad $\le s$ welches eine Anfangsbedingung und die DGL an $t_{ij}$ erfüllt. Suche $q_i \in \mathcal{P}_s([t_i, t_i + h_i])$ mit

\begin{itemize}
	\item $q_i(t_i) = y_i$
	\item $\dot{q}_i(t_{ij}) = f(t_{ij}, q_i(t_{ij}))\;\;\;\;\;j=1,\ldots,s\;\;\;\;\;\;t_{ij} \in [t_i, t_i + h_i]$
\end{itemize}

Setze $y_{i+1} = q_i(t_{i+1})$.

Umsetzung: 

$$\dot{q}_i \in \mathcal{P}_{s-1} \Rightarrow \dot{q}_i(t) = \sum_{l=1}^s k_l L_l(t)\;\;\;\;k_l = \dot{q}_i(t_i)$$
$$L_l \in \mathcal{P}_{s-1}\left(\left[t_i, t_i + h_i\right]\right)\;\;\;\;\;\;\;\;\;\;L_l(t_{ij}) = \delta_{lj}$$

Des Weiteren gilt:

$$q_i(t) = \int_{t_i}^t\!\dot{q}_i(t) \operatorname{d}t + q_i(t_i)$$
$$q_i(t_{ij}) = y_i + \sum_{l=1}^s k_i \int_{t_i}^{t_{ij}}\! L_l(t) \operatorname{d}t$$

Seien $t_{ij} = t_i + \alpha_j h_i$ mit $0 \le \alpha_1 < \alpha_2 < \dots < \alpha_s \le 1$.

$$\Rightarrow q_i(t_{ij}) = y_i + \sum_{l=1}^s k_l \int_{0}^{\alpha_j}\! \hat{L}_l(t) \operatorname{d}t \cdot h_i$$

mit 

$$\hat{L}_l \in \mathcal{P}_{s-1}([0,1])\;\;\;\;\;\;\hat{L}_l = \delta_{lj}$$

Setze für $\alpha_l, l = 1,\;\; \dots, s,\;\; 0 \le \alpha_1 < \alpha_2 < \dots < \alpha_s \le 1$:

$$\gamma_l = \int_0^1\!\hat{L}_l(t)\operatorname{d}t$$
$$\beta_{jl} = \int_0^{\alpha_j}\!\hat{L}_l(t)\operatorname{d}t$$

Dann ist das Kollokationsverfahren äquivalent mit dem so definierten RKV.

\begin{align*}
	\dot{q}_i(t_{ij}) &= k_j = f(t_i + \alpha_j h_i, y_i + h_i \sum_{l=1}^s \beta_{jl} k_l)\\
	y_{i+1} &= q_i(t_i + h_i) = y_i + h_i \sum_{l=1}^s \gamma_l k_l
\end{align*}

% 9. Juli 2010

\begin{theorem} Ordnung.

	Seien $\alpha_j \in [0, 1]$ paarweise verschiedene Knoten einer Quadraturformel über $[0,1]$ mit den Gewichten $\gamma_j\;\;1 \le j \le s$, dann definiert die Wahl 

	$$\beta_{jl} = \displaystyle\int_0^{\alpha_j}\!\hat{L}_l(t) \operatorname{d}t$$

	ein RKV der Ordnung $p$, wobei $p-1$ der Exaktheitsgrad der Quadraturformel ist.
\end{theorem}

Beweisidee: Betrachte die Integralgleichung und verwende Satz I.1.

\begin{example}\*
	\begin{enumerate}
		\item Trapezregel (Lobatho III.A)
		
			$$\begin{array}{c|cc}
				0 & 0 & 0\\
				1 & \frac{1}{2} & \frac{1}{2}\\
				\hline
				  & \frac{1}{2} & \frac{1}{2}
			\end{array}$$
		\item Radau I.A
		
			$$\begin{array}{c|cc}
				0 & 0 & 0\\
				\frac{2}{3} & \frac{1}{3} & \frac{1}{3}\\
				\hline
				  & \frac{1}{4} & \frac{3}{4}
			\end{array}$$

			\begin{align*}
				\hat{L}_1(t) &= 1 - \frac{3}{2}t\\
				\int_0^1\!\hat{L}_1(t) \operatorname{d}t &= \frac{1}{4}\\
				\hat{L}_2(t) &= \frac{3}{2}t\\
				\int_0^1\!\hat{L}_2(t) \operatorname{d}t &= \frac{3}{4}\\
			\end{align*}
			
	\end{enumerate}
\end{example}

Folgerung: 
\begin{enumerate}
	\item Jedes Kolokationsverfahren der Stufe $s \ge 5$ ist implizit
	\item Es existiert ein RKV der Stufe $s$ und der Ordnung $p=2s$ (Zusatz: Die maximal erreichbare Ordnung ist $2s$ und es gibt genau ein Verfahren der Ordnung $p=2s$)
\end{enumerate}

\subsubsection{Schrittweitensteuerung und eingebettete Runge-Kutta-Verfahren}

Alle bisher gezeigten numerischen Ergebnisse basieren auf der Wahl $h_i = h$. Damit sind sie wenig effizient und werden so in der Praxis kaum verwendet.

\paragraph{Schrittweitensteuerung}

Vorüberlegung: Für den Fehler am Endzeitpunkt soll gelten:

$$\|y(T) - y_{N_h}\| \le (T-t_o)\epsilon$$

Die Stabilität garantiert, dass eine grobe Abschätzung erhalten wird durch Aufsummation der lokalen Fehler.

$$\sum_{j=1}^{N_h-1} \| \delta(t_j, y_j, h_j) \|$$

Fordert man nun 

$$\|\delta(t_j, y_j, h_j)\| \le \epsilon h_j$$

so ergibt sich

$$\sum_{j=1}^{N_h-1} \|\delta(t_j, y_j, h_j)\| \le \epsilon (T-t_o)$$

Achtung: $\delta(t_j, y_j, h_j)$ ist nicht berechenbar. Um $\delta(t_j, y_j, h_j)$ abschätzen zu können, wird eine zweite numerische Approximation benötigt.

\begin{itemize}
	\item 1. Möglichkeit: Verwende die gleiche Methode, aber 2 Schritte mit $h_j/2$ $\rightarrow$ aufwendig.
	\item 2. Möglichkeit: Verwende ein 2. Verfahren mit $\hat{p} > p$
		$$z(t_j + h_j) = y_{i+1} + c(t_j)h_j^{p+1} + O(h_j^{p+2})$$
		$$z(t_j + h_j) = \hat{y}_{i+1} + \hat{c}(t_j)h_j^{\hat{p}+1} + O(h_j^{\hat{p}+2})$$
		$$\Rightarrow \hat{y}_{i+1} - y_{i+1} = c(t_j) h_j^{p+1} + O(h_j^{p+2})$$
		Und somit gilt in erster Näherung:
		$$\|\delta(t_j, y_i, h_j)\| \approx \|s(h_j)\| := \|y_{i+1} - \hat{y}_{i+1}\|$$
\end{itemize}

\paragraph{Grundalgorithmus zur Schrittweitensteuerung}
\begin{align*}
	&\text{Eingabe: } t_0, y_0, T, f_0, h_0\\
	&\text{Parameter: } h_{min}, h_{max}, \alpha_{min}, \alpha_{max}, \beta\\
	&j = 0, 1, 2, \dots\\
	&\;\;t_{j+1} = t_j + h\\
	&\;\;\text{Berechne } y_{i+1}, \hat{y}_{i+1} und s(h_j) = \hat{y}_{i+1} - y_{i+1}\\
	&\;\;\text{Definiere } q(h_j) := \frac{\|s(h_j)\|}{s h_j}\\
	&\;\;\alpha = max(\alpha_{min}, \frac{1}{\sqrt[\infty]{q(h_j)}}); \alpha = min(\alpha_{max}, \alpha)\\
	&\;\;h_{neu} = max(h_{min}, \beta \alpha h_j); h_neu = min(h_{max}, h_{neu})\\
	&\;\;\text{Falls } 
\end{align*}

\begin{itemize}
	\item Falls $q(h_j) \le 1$ oder $h_j = h_{min}$, so akteptiere den Schritt.
	\item Falls $t_{j+1} = T$, so ist $y^{(j+1)}$ die Approximation von $y(T)$.
	\item Falls $t_{j+1} < T$, so gehe zu $j+1$ über und setze $h_{j+1} = min(h_{neu}, T - t_{j+1})$.
	\item Falls $q(h_j) > 1$, so liegt ein Fehlversuch vor und der j-te Schritt wird wiederholt $h_j = h_{neu}$
\end{itemize}

Bemerkung:
\begin{enumerate}
	\item $\alpha_{max} \in [1.5, 2]$
	\item $\alpha_{min} \in [0.2, 0.5]$
	\item $\beta \in [0.9, 0.95]$
	\item $h_{min}$ ist wichtig, um ein ``Festfressen'' zu verhindern!
\end{enumerate}

\begin{definition}
	[Definition III.6] Ein explizites RKV$p(\hat p)$ hat die Form:
	$$\begin{array}{c|ccc}
			\alpha_1 & \beta_{11} & \dots & \beta_{1s} \\
			\vdots   & \vdots     &       & \vdots \\
			\alpha_s & \beta_{s1} & \dots & \beta_{ss} \\
			\hline & \gamma_{1} & \dots & \gamma_{s} \\
			\hline & \hat \gamma_{1}& \ldots & \hat \gamma_{s}
		\end{array}$$
		Mit $y^{i+1}=y^{i}+h_{i}\sum_{l=1}^{s}\gamma_{l}k_{l}$ und $\hat y^{i+1}= y^{i}+ h_{i}\sum_{l=1}^{s}\hat \gamma_{l}k_{l}$.
		Zur Berechnung der $k_{l}$ werden die $y^{i}$ verwendet. Ein RKV heißt FSAL (first same as last), falls $k_{1}^{neu}=k_{s}^{alt}$.
\end{definition}

\begin{remark}
	FSAL
	\begin{itemize}
		\item Ein RKV ist genau dann ein FSAL, falls $\gamma_{l}=\beta_{s,l}$ für $l=1,\ldots,s$
		\begin{eqnarray*}
			k_{s}^{alt} &=& f(t_{i}+\alpha_{s}h_{i},y^{i}+h_{i}\sum_{l=1}^{s}\beta_{s,l}k_{l}^{alt})\\
			k_{1}^{neu} &=&f(t_{i}+h_{i},y^{i+1})=f(t_{i}+h_{i},y^{i}+h_{i}\sum_{l=1}^{s}\gamma_{l}k_{l}^{alt})
		\end{eqnarray*}
		\item Ein $s$-stufiges explizites FSAL ist so aufwendig, wie ein $(s-1)$-stufiges explizites RKV
	\end{itemize}
	
	Damit eignen sich eingebettete RKV und insbesondere FSAL hervorragend zur Schrittweitensteuerung.
	Viele frühe Varianten stammen von Fehlberg und sind RKV$p(p+1)$. Diese werden heute kaum noch verwendet, da:
	\begin{itemize}
		\item das Verfahren geringerer Ordnung liefert die Approximation
		\item die Koeffizienten werden so bestimmt, dass der führende Fehlerterm der Ordnung $p$ minimiert wird $\Rightarrow$ Unterschätzung
		des Fehlers $\Rightarrow$ zu optimistisches $h$
	\end{itemize}
	Moderne Verfahren sind RKV$p(\hat p)$, $p>\hat p$. Diese Varianten gehen auf Dormand und Prince zurück. Vorteile gegenüber Fehlberg:
	\begin{itemize}
		\item Das Verfahren höherer Ordnung bestimmt die Approximation
		\item Die Koeffizienten werden bzgl. der höheren Ordnung optimiert
		\item Die Schrittweitenwahl ist der eher sicherheitsorientiert
	\end{itemize}
\end{remark}

\subsection{Lineare Mehrschrittverfahren (MSV)}
\begin{definition}
	[Definition IV.7] Lineare MSV
	\\
	Ein lineares $k$-Schritt-Verfahren hat die Form
	$$y^{i+1}=\sum_{j=0}^{k-1}a_{j}y^{i-j} + h\sum_{j=-1}^{k-1}b_{j}\underbrace{f(t_{i-j},y^{i-j})}_{f_{i-j}}$$
	$a_{j},b_{j},b_{-1}\in \mathbb{R},a_{k-1}\not = 0$ oder $b_{k-1}\not = 0$.
	\\
	Achtung: MSV benötigen eine Anlaufrechnung
\end{definition}

\begin{example} MSV
	\begin{enumerate}
		\item $y^{i+1}=y^{i-1}+2hf(t_{i},y^{i})$ ist ein 2-Schrittverfahren mit den Koeffizienten $a_{0}=0,a_{1}=1,b_{-1}=0,b_{0}=2,b_{1}=0$
		und ist ein explizites Verfahren.
		\item $y^{i+1}=y^{i-1}+\frac{1}{3}h(f_{i-1}+4f_{i}+f_{i+1})$ ist ein 2-Schrittverfahren mit $a_{0}=0,a_{1}=1,b_{-1}=\frac{1}{3},b_{0}=\frac{4}{3},b_{1}=\frac{1}{3}$.
	\end{enumerate}
\end{example}

\begin{remark}
	Das MSV heißt implizit, falls $b_{-1}\not = 0$ ist, sonst explizit.
\end{remark}

Es gibt 2 große Klassen von linearen MSV
\begin{itemize}
	\item Adams-Verfahren
	\item BDF-Verfahren
\end{itemize}

Beiden Verfahrensklassen liegt die Idee der Polynominterpolation zugrunde. Kombiniert man diese Verfahren geeignet, so entstehen
nichtlineare Varianten, die verbesserte Eigenschaften aufweisen können (z.B. Prädiktor-Korrektor-Verfahren, Blending-Verfahren)

\subsubsection{Adams Verfahren}
Man unterscheidet zwischen expliziten und impliziten Verfahren. Beide Varianten weisen ein ähnliches Konstruktionsprinzip auf.
\begin{enumerate}
	\item Schritt: Betrachte die Integralgleichung $y(t_{i+1})-y(t_{i})=\int_{t_{i}}^{t_{i+1}}f(t,y(t))dt$
	\item Schritt: Ersetze $f$ durch ein Interpolationspolynom $p \in \mathcal{P}_{k-1}$ an den Stellen $t_{l}$ mit $f(t_{l},y^{l})$ mit $l\in I_{k}$
	mit $|I_{k}|=k$. Ersetze zugleich $y(t_{l})$ durch $y^{l}$. $p(t_{l})=f(t_{l},y^{l})$ und $y^{i+1}=y^{i}+\int_{t_{i}}^{t_{i+1}}p(t)dt$
\end{enumerate}

Seien nun $L_{l}\in \mathcal{P}_{k-1},l\in I_{k}$ die Lagrange Interpolationspolynome. So gilt: $$p(t)=\sum_{l\in I_{k}}f(t_{l},y^{l})L_{l}(t)$$
und $$y^{i+1}=y^{i}+\sum_{l\in I_{k}}\int_{t_{i}}^{t_{i+1}}L_{l}(t)f(t_{l},y^{l})dt$$
d.h. für jedes Adams-Verfahren gilt: $a_{0}=1, a_{j}=0,j>0$

\paragraph{Adams-Bashforth (ABV)}
Bei der expliziten Variante wählt man, um ein $k$-Schritt Verfahren zu erhalten: $I_{k}=\{i,i-1,\ldots,i-(k-1)\}$

Für äquidistante Knoten $t_{i}=t_{0}+ih$ gilt:
$$\int_{t_{i}}^{t_{i+1}}L_{j}(t)dt = \int_{t_{i}}^{t_{i+1}}\prod_{l=0,l\not = j}^{k-1}\frac{t-t_{i-l}}{t_{i-j}-t_{i-l}}dt
= \int_{0}^{h}\prod_{l=0,l\not = j}^{k-1}\frac{t+lh}{lh-jh}dt=h\int_{0}^{1}\prod_{l=0,l\not=j}^{k-1}\frac{t+l}{l-j}dt$$

$k$-Schritt-Verfahren:
$$y^{i+1}=y^{i}+h\sum_{j=0}^{k-1}b_{j}^{(k)}f_{i-j},\quad b_{j}^{(k)}=\int_{0}^{1}\prod_{l=0,l\not = j}^{k-1}\frac{t+l}{l-j}dt$$

\begin{example}
Beispiel: $k=2$:
$$y^{i+1}=y^{i}+h(b_{0}^{(2)}f_{i}+b_{1}^{(2)}f_{i-1}),\quad b_{0}^{(2)}=\frac{3}{2},b_{1}^{(2)}=\frac{-1}{2}$$
\end{example}

\begin{remark}
	Will man die Schrittzahl im Lauf des Zeitintervalls variieren, so ist eine Darstellung über die Newton'schen dvidierten Differenzen
	empfehlenswert.
	\begin{eqnarray*}
	y^{i+1}&=&y^{i}+h\cdot \sum_{l=0}^{k-1}\mu_{l}\nabla^{l}f_{i}\\
	\nabla^{0}f_{i}&=f_{i}\\
	\nabla f_{i}&=&f_{i}-f_{i-1}\\
	\nabla^{l} f_{i}&=&\nabla(\nabla^{l-1}f_{i})\\
	\end{eqnarray*}
\end{remark}

\begin{example}
 Beispiel $k=2$
 \begin{eqnarray*}
 	y^{i+1}&=&y^{i}+h(\mu_{0}f_{i}+\mu_{1}(f_{i}-f_{i-1}))\\
 	y^{i+1}&=&y^{i}+h(\underbrace{b_{0}^{(2)}}_{=\frac{3}{2}}f_{i}+\underbrace{b_{1}^{(2)}}_{=-\frac{1}{2}}f_{i-1})\\
 	\mu_{1}&=&\frac{1}{2}\\
 	\mu_{0}&=&1
 \end{eqnarray*}
\end{example}

\paragraph{Adams-Moulton (AMV)}
Bei dieser impliziten Variante wählt man um ein $k$-Schritt Verfahren zu erhalten $I_{k+1}=\{i+1,\ldots,i-(k-1)\}$ und $p\in \mathcal{P}_{k}$
(beim Adams-Bashforth-Verfahren ist das Polynom $p$ vom Grad $k-1$) Mit der analogen Vorgehensweise ergibt sich:
$$y^{i+1}=y^{i}+h\sum_{j=-1}^{k-1}b_{j}^{(k)}f_{i-j},\quad b_{j}^{(k)}=\int_{0}^{1}\prod_{l=-1,l\not =j}^{k-1}\frac{t+l}{l-j}dt$$

\begin{example}
	Beispiel $k=2$ implizites 2 Schrittverfahren
	\begin{eqnarray*}
		b_{-1}^{(2)}&=&\int_{0}^{1}\frac{(t)(t+1)}{2}dt=\frac{5}{12}\\
		b_{0}^{(2)}&=&\int_{0}^{1}(1-t)(1+t)dt=\frac{2}{3}\\
		b_{1}^{(2)}&=&\int_{0}^{1}\frac{(t-1)t}{2}dt=\frac{-1}{12}
	\end{eqnarray*}
\end{example}

Allgemein gilt: $\sum_{j=-1}^{k-1}b_{j}^{(k)}=1=\int_{0}^{1}\sum_{j=-1}^{k-1}L_{l}(x)dx$

\begin{remark} AMV
	\begin{enumerate}
		\item Um die $b_{l}^{k}$ beim AMV zu erhalten, müssen Polynome vom Grad $k$ exakt integriert werden. Bei ABV dagegen Polynome
		vom Grad $(k-1)$
		\item Auch hier existiert eine Darstellung über Newton'sche dividierte Differenzen.
		$$y^{i+1}=y^{i}+h\sum_{l=-1}^{k-1}\tilde\mu_{l}\nabla^{l+1}f_{i+1}$$
	\end{enumerate}
\end{remark}

\subsubsection{BDF (Backward Differentiation Formula)}
Beim BDF wird im Gegensatz zu den Adams-Variaten nicht $f$ durch ein Polynom approximiert, sondern die Lösung $y(t)$ selbst.

Idee: Ersetze $y(t)$ durch ein Interpolationspolynom $p\in \mathcal{P}_{k}$ mit
\begin{itemize}
	\item $p(t_{i-j})=y_{i-j},\quad j=-1,0,\ldots,(k-1)$
	\item $\dot p(t_{i+1}) =f_{i+1}$
\end{itemize}

Das liefert Verfahren der Gestalt:
$$y^{i+1}=\sum_{j=0}^{k-1}a_{j}y^{i-j}+hb_{-1}f_{i+1}$$

\begin{example}
$k=2$
\begin{eqnarray*}
	p(t)&=&y_{i+1}\frac{(t-t_{i})(t-t_{i-1})}{(t_{i+1}-t_{i})(t_{i+1}-t_{i-1})} + y_{i}\frac{(t-t_{i+1})(t-t_{i-1})}{(t_{i}-t_{i+1})(t_{i}-t_{i-1})}
	+y_{i-1}\frac{(t-t_{i+1})(t-t_{i})}{(t_{i-1}-t_{i+1})(t_{i-1}-t_{i})}\\
	\dot p(t)&=&\frac{y_{i+1}}{2h^{2}}(2t-(t_{i}+t_{i-1})-\frac{y_{i}}{h^{2}}(2t-(t_{i-1}+t_{i+1}))+\frac{y_{i-1}}{2h^{2}}(2t-(t_{i}+t_{i+1}))\\
	\dot p(t_{i+1})&=&\frac{y_{i+1}}{2h^{2}}\cdot 3h - \frac{y_{i}}{h^{2}}\cdot 2 h+\frac{y_{i-1}}{2h^{2}}h=f_{i+1}\\
	y_{i+1}&=&\frac{4}{3}y_{i}-\frac{1}{3}y_{i-1}+\frac{2}{3}hf_{i+1}	
\end{eqnarray*}
\end{example}

Achtung: Für $k>6$ sind die BDF nicht konvergent

\subsubsection{Konvergenz von linearen MSV}

\begin{example}
$$y^{i+1}=4y^{i}-3y^{i-1}-2hf_{i-1}$$
Wende das Verfahren an auf $\dot y =0,y^{0}=1,y^{1}=1+\epsilon h$
\begin{eqnarray*}
	y^{2}&=&4(1+\epsilon h)-3\cdot 1 = 1+4\epsilon h\\
	y^{3}&=&4(1+4\epsilon h)-3(1+\epsilon h) = 1+13\epsilon h\\
	y^{i}&=&1+\frac{3^{i}-1}{2}\epsilon h
\end{eqnarray*}
Sei $h=\frac{1}{N}$, dann gilt $y^{N}$ approximiert $y$ an der Stelle $t_{0}+1$ und $y^{N}\rightarrow \infty$ für $N\rightarrow \infty$
\end{example}

\subsubsection{Null-Stabilität}
\begin{definition}
	[Definition IV.8] Ein lineares MSV heißt Nullstabil falls für alle $y^{0},\ldots,y^{k-1}$ mit $||y^{l}||\le 1$, $l=0,\ldots,k-1$ ein
	$M<\infty$ existiert mit $||y^{i}||\le M$ wobei $y^{i}=\sum_{l=0}^{k-1}a_{l}y^{i-l}$ (Lösung von $\dot y(t)=0$)
\end{definition}

\begin{definition}
	[Definition IV.9] Charakteristische Polynome
	\\
	\begin{enumerate}
		\item 1. Charakteristisches Polynom: $\rho(r)=r^{k}-\sum_{l=0}^{k-1}a_{l}r^{k-1-l}$
		\item 2. Charakteristisches Polynom: $\sigma(r)=b_{-1}r^{k}+\sum_{l=0}^{k-1}b_{l}r^{k-1-l}$
	\end{enumerate}
\end{definition}


\begin{example}
	\begin{enumerate}
		\item Das vorherige Gegenbeispiel liefert: $\rho(r)=r^{2}-4r+3=(r-1)(r-3)$
		\item Adams-Verfahren: $\rho(r)=r^{k}-r^{k-1}=r^{k-1}(r-1)$
		\item BDF mit $k=2$: $\rho(r)=r^{2}-\frac{4}{3}r+\frac{1}{3} = (r-1)(r-\frac{1}{3})$
	\end{enumerate}
\end{example}

\begin{theorem}
	Wurzelbedingung
	\\
	Ein lineares MSV ist genau dann Null-stabil, falls die Wurzelbedingung erfüllt ist, d.h. alle Nullstellen $r_{i}$, $i=1,\ldots,k$
	von $\rho(r)$ gilt:
	\begin{enumerate}
		\item $|r_{i}|\le 1$
		\item Falls $|r_{i}|=1\Rightarrow \dot \rho(r_{i})\not = 0$ (d.h. wenn die Nullstelle auf dem Rand des Einheitskreises liegt, dann muss sie einfach sein)
	\end{enumerate}
\end{theorem}

\subsubsection{Konsistenz}
\begin{definition}
	[Definition IV.10] ein lineares MSV heißt konsistent, von der Ordnung $p$, falls 
	$$z(t_{i+1})-\sum_{j=0}^{k-1}a_{j}z(t_{i-j})-h(\sum_{j=-1}^{k-1}b_{j}\dot z(t_{i-j}))=O(h^{p+1})$$
\end{definition}

\begin{theorem}
	Konsistenz
	\\
	\begin{enumerate}
		\item Ein lineares MSV ist genau dann konsistent, falls $\sum_{j=0}^{k-1}a_{j}=1$ und $\sum_{j=0}^{k-1}(-j)a_{j}+\sum_{j=-1}^{k-1}b_{j}=1$
		\item Es ist konsistent von der Ordnung $p$ genau dann, falls zusätzlich gilt: $\sum_{j=0}^{k-1}(-j)^{l}a_{j}+l\cdot \sum_{j=-1}^{k-1}(-j)^{l-1}b_{j}=1$ für $l=2,\ldots,p$
	\end{enumerate}
\end{theorem}

\begin{remark}
	Konsistenz $\Leftrightarrow \rho(1)=0$
\end{remark}

\begin{theorem}
	Konvergenz
	\\
	Sei die Lösung in $C^{p+1}$, so gilt für ein stabiles MSV der Konsistenzordnung $p$:
	$$||y(t_{i}-y^{i}||\le C(h^{p}+\epsilon_{0})$$
	für $i=1,\ldots,N_{k}$ und $h=\frac{T-t_{0}}{N_{h}}$ und $\epsilon_{0}=\max_{l=0,\ldots,k-1}||y(t_{l})-y^{l}||$
\end{theorem}

\begin{remark}
 Dahlquist Kriterium: Die maximale Ordnung eines linearen stabilen $k$-Schritt Verfahrens ist 
 $p=\begin{cases}
 	k+1&k \text{ ungerade}\\
 	k+2&k \text{ gerade}\\
 	k&\text{explizit}
 \end{cases}$
\end{remark}